import java.util.Arrays;

/**
 * 希尔排序
 * 插入排序的优化版
 * 关键：间隔
 */
public class ShellSort {
    public static int[] shellSort(int[] nums) {
        int[] res = Arrays.copyOf(nums, nums.length);
        int gas = 1;
        // 根据数组长度计算出第一轮的间隔大小
        while (gas < res.length / 3) {
            // 一定要加 1，最后一趟排序就是间隔为 1 个单位的比较
            gas = gas * 3 + 1;
        }
        while (gas > 0) {
            for (int i = gas; i < res.length; i++) {
                // 记录下 temp 值
                int temp = res[i];
                int j = i;
                // 前一间隔的索引未越界，并且当前元素小于前一间隔上的元素
                while (j - gas >= 0 && temp < res[j - gas]) {
                    // 与插入排序类似，较大的元素后移到当前索引上
                    res[j] = res[j - gas];
                    j -= gas;
                }
                // 最终将 temp 元素插入到合适的位置
                res[j] = temp;
            }
            // 缩小间隔
            gas /= 3;
        }
        return res;
    }
}
